package baseclass.l_string;

/**
 * @date 2020/5/31 20:07
 */
public class Code03_RK算法 {
    /**
     * 方式2：RK算法，时间O(M-N)，空间O(1)
     * 思路：s1,s2俩字符串，
     * 对s1中长为N的子串进行hash。s2也hash。
     * 1)若hash值等，有可能 子串和s2等
     * 2)若hash值不等，子串肯定不等
     * <p>
     * 计算s中子串hash，要用到前一个和后一个关系，(1)时间得到
     * <p>
     * 要考虑两个问题：
     * 1)大数问题，用取模计算
     * 2)char c 的取值范围为0~255，计算hash结果时会自动类型提升为int，
     * 为避免符号位扩展，使用 (unsigned int)c & 0x000000FF
     * <p>
     * hash算法：可以用等比求和，可以用数组存储hash值， 那么空间就是O(N)，也可以不存hash值
     * <p>
     * hash(n) = a^(n-1)*s1 + a^(n-2)*s2 + ...+ a*s(n-1)+ 1*sn
     * <p>
     * hash(i) = hash(i-1)*base - a^(i-2)*s1 + si
     */

    public static int strStr2(String str1, String str2) {
        if (str1 == null || str2 == null
                || str1.length() < str2.length()) return -1;
        if (str1.isEmpty()) return 0;
        //非空子串中，查询空串返回的是0
        if(str2.isEmpty()) return 0;

        //26个字符
        int base = 26;
        final long MOD = (long) Math.pow(2, 31);
        long hash1 = charToInt(str1.charAt(0));
        long hash2 = charToInt(str2.charAt(0));
        int m = str1.length();
        int n = str2.length();
        for (int i = 1; i < n; i++) {
            hash1 = (hash1 * base + charToInt(str1.charAt(i))) % MOD;
            hash2 = (hash2 * base + charToInt(str2.charAt(i))) % MOD;
        }
        if (hash1 == hash2) return str1.substring(0,n).equals(str2) ? 0 : -1;

        long al = 1; //base ^ n
        for (int i = 0; i < n; i++) {
            al = (al * base) % MOD;
        }

        int len = m - n;
        //0号对比不上，从1号开始对比
        for (int i = 1; i <= len; i++) {
            //先更新hash, 注意虽然al不可能越界，但是al * charToInt可能越界
            hash1 = (hash1 * base - al * charToInt(str1.charAt(i - 1))% MOD
                    + charToInt(str1.charAt(n + i - 1))) % MOD;
            if (hash1 == hash2 && str1.substring(i, n + i).equals(str2))
                return i;
        }
        return -1;
    }

    private static int charToInt(char c) {
        return c - '0';
    }
}
